home *** CD-ROM | disk | FTP | other *** search
/ Aminet 2 / Aminet AMIGA CDROM (1994)(Walnut Creek)[Feb 1994][W.O. 44790-1].iso / Aminet / util / gnu / diff_2_3.lha / diff-2.3 / diff3.c < prev    next >
C/C++ Source or Header  |  1993-05-26  |  49KB  |  1,793 lines
  1. /* Three way file comparison program (diff3) for Project GNU.
  2.    Copyright (C) 1988, 1989, 1992 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2, or (at your option)
  7.    any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17.  
  18. /* Written by Randy Smith */
  19.  
  20. #if __STDC__
  21. #define VOID void
  22. #else
  23. #define VOID char
  24. #endif
  25.  
  26. #include <stdio.h>
  27. #include <ctype.h>
  28. #include "getopt.h"
  29. #include "system.h"
  30.  
  31. #ifdef AMIGA
  32. #include <signal.h>
  33. #include <exec/types.h>
  34. #include <dos/dostags.h>
  35. #include <proto/dos.h>
  36. #include <proto/exec.h>
  37.  
  38. extern struct DosLibrary *DOSBase;
  39. #endif /* AMIGA */
  40.  
  41. /*
  42.  * Internal data structures and macros for the diff3 program; includes
  43.  * data structures for both diff3 diffs and normal diffs.
  44.  */
  45.  
  46. /* Different files within a three way diff.  */
  47. #define    FILE0    0
  48. #define    FILE1    1
  49. #define    FILE2    2
  50.  
  51. /*
  52.  * A three way diff is built from two two-way diffs; the file which
  53.  * the two two-way diffs share is:
  54.  */
  55. #define    FILEC    FILE2
  56.  
  57. /*
  58.  * Different files within a two way diff.
  59.  * FC is the common file, FO the other file.
  60.  */
  61. #define FO 0
  62. #define FC 1
  63.  
  64. /* The ranges are indexed by */
  65. #define    START    0
  66. #define    END    1
  67.  
  68. enum diff_type {
  69.   ERROR,            /* Should not be used */
  70.   ADD,                /* Two way diff add */
  71.   CHANGE,            /* Two way diff change */
  72.   DELETE,            /* Two way diff delete */
  73.   DIFF_ALL,            /* All three are different */
  74.   DIFF_1ST,            /* Only the first is different */
  75.   DIFF_2ND,            /* Only the second */
  76.   DIFF_3RD            /* Only the third */
  77. };
  78.  
  79. /* Two way diff */
  80. struct diff_block {
  81.   int ranges[2][2];        /* Ranges are inclusive */
  82.   char **lines[2];        /* The actual lines (may contain nulls) */
  83.   int *lengths[2];        /* Line lengths (including newlines, if any) */
  84.   struct diff_block *next;
  85. };
  86.  
  87. /* Three way diff */
  88.  
  89. struct diff3_block {
  90.   enum diff_type correspond;    /* Type of diff */
  91.   int ranges[3][2];        /* Ranges are inclusive */
  92.   char **lines[3];        /* The actual lines (may contain nulls) */
  93.   int *lengths[3];        /* Line lengths (including newlines, if any) */
  94.   struct diff3_block *next;
  95. };
  96.  
  97. /*
  98.  * Access the ranges on a diff block.
  99.  */
  100. #define    D_LOWLINE(diff, filenum)    \
  101.   ((diff)->ranges[filenum][START])
  102. #define    D_HIGHLINE(diff, filenum)    \
  103.   ((diff)->ranges[filenum][END])
  104. #define    D_NUMLINES(diff, filenum)    \
  105.   (D_HIGHLINE (diff, filenum) - D_LOWLINE (diff, filenum) + 1)
  106.  
  107. /*
  108.  * Access the line numbers in a file in a diff by relative line
  109.  * numbers (i.e. line number within the diff itself).  Note that these
  110.  * are lvalues and can be used for assignment.
  111.  */
  112. #define    D_RELNUM(diff, filenum, linenum)    \
  113.   ((diff)->lines[filenum][linenum])
  114. #define    D_RELLEN(diff, filenum, linenum)    \
  115.   ((diff)->lengths[filenum][linenum])
  116.  
  117. /*
  118.  * And get at them directly, when that should be necessary.
  119.  */
  120. #define    D_LINEARRAY(diff, filenum)    \
  121.   ((diff)->lines[filenum])
  122. #define    D_LENARRAY(diff, filenum)    \
  123.   ((diff)->lengths[filenum])
  124.  
  125. /*
  126.  * Next block.
  127.  */
  128. #define    D_NEXT(diff)    ((diff)->next)
  129.  
  130. /*
  131.  * Access the type of a diff3 block.
  132.  */
  133. #define    D3_TYPE(diff)    ((diff)->correspond)
  134.  
  135. /*
  136.  * Line mappings based on diffs.  The first maps off the top of the
  137.  * diff, the second off of the bottom.
  138.  */
  139. #define    D_HIGH_MAPLINE(diff, fromfile, tofile, lineno)    \
  140.   ((lineno)                        \
  141.    - D_HIGHLINE ((diff), (fromfile))            \
  142.    + D_HIGHLINE ((diff), (tofile)))
  143.  
  144. #define    D_LOW_MAPLINE(diff, fromfile, tofile, lineno)    \
  145.   ((lineno)                        \
  146.    - D_LOWLINE ((diff), (fromfile))            \
  147.    + D_LOWLINE ((diff), (tofile)))
  148.  
  149. /*
  150.  * General memory allocation function.
  151.  */
  152. #define    ALLOCATE(number, type)    \
  153.   (type *) xmalloc ((number) * sizeof (type))
  154.  
  155. /* Options variables for flags set on command line.  */
  156.  
  157. /* If nonzero, treat all files as text files, never as binary.  */
  158. static int always_text;
  159.  
  160. /* If nonzero, write out an ed script instead of the standard diff3 format.  */
  161. static int edscript;
  162.  
  163. /* If nonzero, in the case of overlapping diffs (type DIFF_ALL),
  164.    preserve the lines which would normally be deleted from
  165.    file 1 with a special flagging mechanism.  */
  166. static int flagging;
  167.  
  168. /* Number of lines to keep in identical prefix and suffix.  */
  169. static int horizon_lines = 10;
  170.  
  171. /* If nonzero, do not output information for overlapping diffs.  */
  172. static int simple_only;
  173.  
  174. /* If nonzero, do not output information for non-overlapping diffs.  */
  175. static int overlap_only;
  176.  
  177. /* If nonzero, show information for DIFF_2ND diffs.  */
  178. static int show_2nd;
  179.  
  180. /* If nonzero, include `:wq' at the end of the script
  181.    to write out the file being edited.   */
  182. static int finalwrite;
  183.  
  184. /* If nonzero, output a merged file.  */
  185. static int merge;
  186.  
  187. static char *argv0;
  188.  
  189. /*
  190.  * Forward function declarations.
  191.  */
  192. static int myread ();
  193. static void fatal ();
  194. static void perror_with_exit ();
  195. static struct diff_block *process_diff ();
  196. static struct diff3_block *make_3way_diff ();
  197. static void output_diff3 ();
  198. static int output_diff3_edscript ();
  199. static int output_diff3_merge ();
  200. static void usage ();
  201.  
  202. static struct diff3_block *using_to_diff3_block ();
  203. static int copy_stringlist ();
  204. static struct diff3_block *create_diff3_block ();
  205. static int compare_line_list ();
  206.  
  207. static char *read_diff ();
  208. static enum diff_type process_diff_control ();
  209. static char *scan_diff_line ();
  210.  
  211. static struct diff3_block *reverse_diff3_blocklist ();
  212.  
  213. VOID *xmalloc ();
  214. static VOID *xrealloc ();
  215.  
  216. static char diff_program[] = DIFF_PROGRAM;
  217.  
  218. static struct option longopts[] =
  219. {
  220.   {"text", 0, NULL, 'a'},
  221.   {"show-all", 0, NULL, 'A'},
  222.   {"ed", 0, NULL, 'e'},
  223.   {"show-overlap", 0, NULL, 'E'},
  224.   {"label", 1, NULL, 'L'},
  225.   {"merge", 0, NULL, 'm'},
  226.   {"overlap-only", 0, NULL, 'x'},
  227.   {"easy-only", 0, NULL, '3'},
  228.   {"version", 0, NULL, 'v'},
  229.   {0, 0, 0, 0}
  230. };
  231.  
  232. /*
  233.  * Main program.  Calls diff twice on two pairs of input files,
  234.  * combines the two diffs, and outputs them.
  235.  */
  236. int
  237. main (argc, argv)
  238.      int argc;
  239.      char **argv;
  240. {
  241.   extern char *version_string;
  242.   int c, i;
  243.   int mapping[3];
  244.   int rev_mapping[3];
  245.   int incompat;
  246.   int conflicts_found;
  247.   struct diff_block *thread0, *thread1, *last_block;
  248.   struct diff3_block *diff3;
  249.   int tag_count = 0;
  250.   char *tag_strings[3];
  251.   extern char *optarg;
  252.   char *commonname;
  253.   char **file;
  254.   struct stat statb;
  255.  
  256. #ifdef AMIGA
  257.   if (DOSBase->dl_lib.lib_Version < 37) {
  258.     fputs ("Need Amiga OS 2.0 (V.37) to execute.\n", stderr);
  259.     exit (20);
  260.   }
  261. #endif /* AMIGA */
  262.  
  263.   incompat = 0;
  264.  
  265.   argv0 = argv[0];
  266.  
  267.   while ((c = getopt_long (argc, argv, "aeimvx3AEXL:", longopts, (int *) 0))
  268.      != EOF)
  269.     {
  270.       switch (c)
  271.     {
  272.     case 'a':
  273.       always_text = 1;
  274.       break;
  275.     case 'A':
  276.       show_2nd = 1;
  277.       flagging = 1;
  278.       incompat++;
  279.       break;
  280.     case 'x':
  281.       overlap_only = 1;
  282.       incompat++;
  283.       break;
  284.     case '3':
  285.       simple_only = 1;
  286.       incompat++;
  287.       break;
  288.     case 'i':
  289.       finalwrite = 1;
  290.       break;
  291.     case 'm':
  292.       merge = 1;
  293.       break;
  294.     case 'X':
  295.       overlap_only = 1;
  296.       /* Falls through */
  297.     case 'E':
  298.       flagging = 1;
  299.       /* Falls through */
  300.     case 'e':
  301.       incompat++;
  302.       break;
  303.     case 'v':
  304.       fprintf (stderr, "GNU diff3 version %s\n", version_string);
  305.       break;
  306.     case 'L':
  307.       /* Handle up to three -L options.  */
  308.       if (tag_count < 3)
  309.         {
  310.           tag_strings[tag_count++] = optarg;
  311.           break;
  312.         }
  313.       /* Falls through */
  314.     default:
  315.       usage ();
  316.       /* NOTREACHED */
  317.     }
  318.     }
  319.  
  320.   edscript = incompat & ~merge;  /* -AeExX3 without -m implies ed script.  */
  321.   show_2nd |= ~incompat & merge;  /* -m without -AeExX3 implies -A.  */
  322.   flagging |= ~incompat & merge;
  323.  
  324.   if (incompat > 1  /* Ensure at most one of -AeExX3.  */
  325.       || finalwrite & merge /* -i -m would rewrite input file.  */
  326.       || (tag_count && ! flagging) /* -L requires one of -AEX.  */
  327.       || argc - optind != 3)
  328.     usage ();
  329.  
  330.   file = &argv[optind];
  331.  
  332.   for (i = tag_count; i < 3; i++)
  333.     tag_strings[i] = file[i];
  334.  
  335.   /* Always compare file1 to file2, even if file2 is "-".
  336.      This is needed for -mAeExX3.  Using the file0 as
  337.      the common file would produce wrong results, because if the
  338.      file0-file1 diffs didn't line up with the file0-file2 diffs
  339.      (which is entirely possible since we don't use diff's -n option),
  340.      diff3 might report phantom changes from file1 to file2.  */
  341.  
  342.   if (strcmp (file[2], "-") == 0)
  343.     {
  344.       /* Sigh.  We've got standard input as the last arg.  We can't
  345.      call diff twice on stdin.  Use the middle arg as the common
  346.      file instead.  */
  347.       if (strcmp (file[0], "-") == 0 || strcmp (file[1], "-") == 0)
  348.     fatal ("`-' specified for more than one input file");
  349.       mapping[0] = 0;
  350.       mapping[1] = 2;
  351.       mapping[2] = 1;
  352.     }
  353.   else
  354.     {
  355.       /* Normal, what you'd expect */
  356.       mapping[0] = 0;
  357.       mapping[1] = 1;
  358.       mapping[2] = 2;
  359.     }
  360.  
  361.   for (i = 0; i < 3; i++)
  362.     rev_mapping[mapping[i]] = i;
  363.  
  364.   for (i = 0; i < 3; i++)
  365.     if (strcmp (file[i], "-") != 0)
  366.       if (stat (file[i], &statb) < 0)
  367.     perror_with_exit (file[i]);
  368.       else if (S_ISDIR(statb.st_mode))
  369.     {
  370.       fprintf (stderr, "%s: %s: Is a directory\n", argv0, file[i]);
  371.       exit (2);
  372.     }
  373.  
  374.  
  375.   commonname = file[rev_mapping[FILEC]];
  376.   thread1 = process_diff (file[rev_mapping[FILE1]], commonname, &last_block);
  377.   if (thread1)
  378.     for (i = 0; i < 2; i++)
  379.       {
  380.     horizon_lines = max (horizon_lines, D_NUMLINES (thread1, i));
  381.     horizon_lines = max (horizon_lines, D_NUMLINES (last_block, i));
  382.       }
  383.   thread0 = process_diff (file[rev_mapping[FILE0]], commonname, &last_block);
  384.   diff3 = make_3way_diff (thread0, thread1);
  385.   if (edscript)
  386.     conflicts_found
  387.       = output_diff3_edscript (stdout, diff3, mapping, rev_mapping,
  388.                    tag_strings[0], tag_strings[1], tag_strings[2]);
  389.   else if (merge)
  390.     {
  391.       if (! freopen (file[rev_mapping[FILE0]], "r", stdin))
  392.     perror_with_exit (file[rev_mapping[FILE0]]);
  393.       conflicts_found
  394.     = output_diff3_merge (stdin, stdout, diff3, mapping, rev_mapping,
  395.                   tag_strings[0], tag_strings[1], tag_strings[2]);
  396.       if (ferror (stdin))
  397.     fatal ("read error");
  398.     }
  399.   else
  400.     {
  401.       output_diff3 (stdout, diff3, mapping, rev_mapping);
  402.       conflicts_found = 0;
  403.     }
  404.  
  405.   if (ferror (stdout) || fclose (stdout) != 0)
  406.     fatal ("write error");
  407.   exit (conflicts_found);
  408.   return conflicts_found;
  409. }
  410.  
  411. /*
  412.  * Explain, patiently and kindly, how to use this program.  Then exit.
  413.  */
  414. static void
  415. usage ()
  416. {
  417.   fprintf (stderr, "\
  418. Usage: %s [options] my-file older-file your-file\n\
  419. Options:\n\
  420.        [-exAEX3v] [-i|-m] [-L label1 [-L label2 [-L label3]]] [--text] [--ed]\n\
  421.        [--merge] [--show-all] [--show-overlap] [--overlap-only] [--easy-only]\n\
  422.        [--label=label1 [--label=label2 [--label=label3]]] [--version]\n\
  423.        Only one of [exAEX3] is allowed\n", argv0);
  424.   exit (2);
  425. }
  426.  
  427. /*
  428.  * Routines that combine the two diffs together into one.  The
  429.  * algorithm used follows:
  430.  *
  431.  *   File2 is shared in common between the two diffs.
  432.  *   Diff02 is the diff between 0 and 2.
  433.  *   Diff12 is the diff between 1 and 2.
  434.  *
  435.  *    1) Find the range for the first block in File2.
  436.  *        a) Take the lowest of the two ranges (in File2) in the two
  437.  *           current blocks (one from each diff) as being the low
  438.  *           water mark.  Assign the upper end of this block as
  439.  *           being the high water mark and move the current block up
  440.  *           one.  Mark the block just moved over as to be used.
  441.  *        b) Check the next block in the diff that the high water
  442.  *           mark is *not* from.
  443.  *
  444.  *           *If* the high water mark is above
  445.  *           the low end of the range in that block,
  446.  *
  447.  *           mark that block as to be used and move the current
  448.  *           block up.  Set the high water mark to the max of
  449.  *           the high end of this block and the current.  Repeat b.
  450.  *
  451.  *     2) Find the corresponding ranges in File0 (from the blocks
  452.  *        in diff02; line per line outside of diffs) and in File1.
  453.  *        Create a diff3_block, reserving space as indicated by the ranges.
  454.  *
  455.  *     3) Copy all of the pointers for file2 in.  At least for now,
  456.  *        do bcmp's between corresponding strings in the two diffs.
  457.  *
  458.  *     4) Copy all of the pointers for file0 and 1 in.  Get what you
  459.  *        need from file2 (when there isn't a diff block, it's
  460.  *        identical to file2 within the range between diff blocks).
  461.  *
  462.  *     5) If the diff blocks you used came from only one of the two
  463.  *        strings of diffs, then that file (i.e. the one other than
  464.  *        the common file in that diff) is the odd person out.  If you used
  465.  *        diff blocks from both sets, check to see if files 0 and 1 match:
  466.  *
  467.  *        Same number of lines?  If so, do a set of bcmp's (if a
  468.  *        bcmp matches; copy the pointer over; it'll be easier later
  469.  *        if you have to do any compares).  If they match, 0 & 1 are
  470.  *        the same.  If not, all three different.
  471.  *
  472.  *   Then you do it again, until you run out of blocks.
  473.  *
  474.  */
  475.  
  476. /*
  477.  * This routine makes a three way diff (chain of diff3_block's) from two
  478.  * two way diffs (chains of diff_block's).  It is assumed that each of
  479.  * the two diffs passed are onto the same file (i.e. that each of the
  480.  * diffs were made "to" the same file).  The three way diff pointer
  481.  * returned will have numbering FILE0--the other file in diff02,
  482.  * FILE1--the other file in diff12, and FILEC--the common file.
  483.  */
  484. static struct diff3_block *
  485. make_3way_diff (thread0, thread1)
  486.      struct diff_block *thread0, *thread1;
  487. {
  488. /*
  489.  * This routine works on the two diffs passed to it as threads.
  490.  * Thread number 0 is diff02, thread number 1 is diff12.  The USING
  491.  * array is set to the base of the list of blocks to be used to
  492.  * construct each block of the three way diff; if no blocks from a
  493.  * particular thread are to be used, that element of the using array
  494.  * is set to 0.  The elements LAST_USING array are set to the last
  495.  * elements on each of the using lists.
  496.  *
  497.  * The HIGH_WATER_MARK is set to the highest line number in the common file
  498.  * described in any of the diffs in either of the USING lists.  The
  499.  * HIGH_WATER_THREAD names the thread.  Similarly the BASE_WATER_MARK
  500.  * and BASE_WATER_THREAD describe the lowest line number in the common file
  501.  * described in any of the diffs in either of the USING lists.  The
  502.  * HIGH_WATER_DIFF is the diff from which the HIGH_WATER_MARK was
  503.  * taken.
  504.  *
  505.  * The HIGH_WATER_DIFF should always be equal to LAST_USING
  506.  * [HIGH_WATER_THREAD].  The OTHER_DIFF is the next diff to check for
  507.  * higher water, and should always be equal to
  508.  * CURRENT[HIGH_WATER_THREAD ^ 0x1].  The OTHER_THREAD is the thread
  509.  * in which the OTHER_DIFF is, and hence should always be equal to
  510.  * HIGH_WATER_THREAD ^ 0x1.
  511.  *
  512.  * The variable LAST_DIFF is kept set to the last diff block produced
  513.  * by this routine, for line correspondence purposes between that diff
  514.  * and the one currently being worked on.  It is initialized to
  515.  * ZERO_DIFF before any blocks have been created.
  516.  */
  517.  
  518.   struct diff_block
  519.     *using[2],
  520.     *last_using[2],
  521.     *current[2];
  522.  
  523.   int
  524.     high_water_mark;
  525.  
  526.   int
  527.     high_water_thread,
  528.     base_water_thread,
  529.     other_thread;
  530.  
  531.   struct diff_block
  532.     *high_water_diff,
  533.     *other_diff;
  534.  
  535.   struct diff3_block
  536.     *result,
  537.     *tmpblock,
  538.     **result_end,
  539.     *last_diff3;
  540.  
  541.   static struct diff3_block zero_diff3 = {
  542.       ERROR,
  543.       { {0, 0}, {0, 0}, {0, 0} },
  544.       { (char **) 0, (char **) 0, (char **) 0 },
  545.       { (int *) 0, (int *) 0, (int *) 0 },
  546.       (struct diff3_block *) 0
  547.       };
  548.  
  549.   /* Initialization */
  550.   result = 0;
  551.   result_end = &result;
  552.   current[0] = thread0; current[1] = thread1;
  553.   last_diff3 = &zero_diff3;
  554.  
  555.   /* Sniff up the threads until we reach the end */
  556.  
  557.   while (current[0] || current[1])
  558.     {
  559.       using[0] = using[1] = last_using[0] = last_using[1] =
  560.     (struct diff_block *) 0;
  561.  
  562.       /* Setup low and high water threads, diffs, and marks.  */
  563.       if (!current[0])
  564.     base_water_thread = 1;
  565.       else if (!current[1])
  566.     base_water_thread = 0;
  567.       else
  568.     base_water_thread =
  569.       (D_LOWLINE (current[0], FC) > D_LOWLINE (current[1], FC));
  570.  
  571.       high_water_thread = base_water_thread;
  572.  
  573.       high_water_diff = current[high_water_thread];
  574.  
  575. #if 0
  576.       /* low and high waters start off same diff */
  577.       base_water_mark = D_LOWLINE (high_water_diff, FC);
  578. #endif
  579.  
  580.       high_water_mark = D_HIGHLINE (high_water_diff, FC);
  581.  
  582.       /* Make the diff you just got info from into the using class */
  583.       using[high_water_thread]
  584.     = last_using[high_water_thread]
  585.     = high_water_diff;
  586.       current[high_water_thread] = high_water_diff->next;
  587.       last_using[high_water_thread]->next
  588.     = (struct diff_block *) 0;
  589.  
  590.       /* And mark the other diff */
  591.       other_thread = high_water_thread ^ 0x1;
  592.       other_diff = current[other_thread];
  593.  
  594.       /* Shuffle up the ladder, checking the other diff to see if it
  595.      needs to be incorporated.  */
  596.       while (other_diff
  597.          && D_LOWLINE (other_diff, FC) <= high_water_mark + 1)
  598.     {
  599.  
  600.       /* Incorporate this diff into the using list.  Note that
  601.          this doesn't take it off the current list */
  602.       if (using[other_thread])
  603.         last_using[other_thread]->next = other_diff;
  604.       else
  605.         using[other_thread] = other_diff;
  606.       last_using[other_thread] = other_diff;
  607.  
  608.       /* Take it off the current list.  Note that this following
  609.          code assumes that other_diff enters it equal to
  610.          current[high_water_thread ^ 0x1] */
  611.       current[other_thread]
  612.         = current[other_thread]->next;
  613.       other_diff->next
  614.         = (struct diff_block *) 0;
  615.  
  616.       /* Set the high_water stuff
  617.          If this comparison is equal, then this is the last pass
  618.          through this loop; since diff blocks within a given
  619.          thread cannot overlap, the high_water_mark will be
  620.          *below* the range_start of either of the next diffs.  */
  621.  
  622.       if (high_water_mark < D_HIGHLINE (other_diff, FC))
  623.         {
  624.           high_water_thread ^= 1;
  625.           high_water_diff = other_diff;
  626.           high_water_mark = D_HIGHLINE (other_diff, FC);
  627.         }
  628.  
  629.       /* Set the other diff */
  630.       other_thread = high_water_thread ^ 0x1;
  631.       other_diff = current[other_thread];
  632.     }
  633.  
  634.       /* The using lists contain a list of all of the blocks to be
  635.      included in this diff3_block.  Create it.  */
  636.  
  637.       tmpblock = using_to_diff3_block (using, last_using,
  638.                        base_water_thread, high_water_thread,
  639.                        last_diff3);
  640.  
  641.       if (!tmpblock)
  642.     fatal ("internal error: screwup in format of diff blocks");
  643.  
  644.       /* Put it on the list.  */
  645.       *result_end = tmpblock;
  646.       result_end = &tmpblock->next;
  647.  
  648.       /* Set up corresponding lines correctly.  */
  649.       last_diff3 = tmpblock;
  650.     }
  651.   return result;
  652. }
  653.  
  654. /*
  655.  * using_to_diff3_block:
  656.  *   This routine takes two lists of blocks (from two separate diff
  657.  * threads) and puts them together into one diff3 block.
  658.  * It then returns a pointer to this diff3 block or 0 for failure.
  659.  *
  660.  * All arguments besides using are for the convenience of the routine;
  661.  * they could be derived from the using array.
  662.  * LAST_USING is a pair of pointers to the last blocks in the using
  663.  * structure.
  664.  * LOW_THREAD and HIGH_THREAD tell which threads contain the lowest
  665.  * and highest line numbers for File0.
  666.  * last_diff3 contains the last diff produced in the calling routine.
  667.  * This is used for lines mappings which would still be identical to
  668.  * the state that diff ended in.
  669.  *
  670.  * A distinction should be made in this routine between the two diffs
  671.  * that are part of a normal two diff block, and the three diffs that
  672.  * are part of a diff3_block.
  673.  */
  674. static struct diff3_block *
  675. using_to_diff3_block (using, last_using, low_thread, high_thread, last_diff3)
  676.      struct diff_block
  677.        *using[2],
  678.        *last_using[2];
  679.      int low_thread, high_thread;
  680.      struct diff3_block *last_diff3;
  681. {
  682.   int low[2], high[2];
  683.   struct diff3_block *result;
  684.   struct diff_block *ptr;
  685.   int d, i;
  686.  
  687.   /* Find the range in the common file.  */
  688.   int lowc = D_LOWLINE (using[low_thread], FC);
  689.   int highc = D_HIGHLINE (last_using[high_thread], FC);
  690.  
  691.   /* Find the ranges in the other files.
  692.      If using[d] is null, that means that the file to which that diff
  693.      refers is equivalent to the common file over this range.  */
  694.  
  695.   for (d = 0; d < 2; d++)
  696.     if (using[d])
  697.       {
  698.     low[d] = D_LOW_MAPLINE (using[d], FC, FO, lowc);
  699.     high[d] = D_HIGH_MAPLINE (last_using[d], FC, FO, highc);
  700.       }
  701.     else
  702.       {
  703.     low[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, lowc);
  704.     high[d] = D_HIGH_MAPLINE (last_diff3, FILEC, FILE0 + d, highc);
  705.       }
  706.  
  707.   /* Create a block with the appropriate sizes */
  708.   result = create_diff3_block (low[0], high[0], low[1], high[1], lowc, highc);
  709.  
  710.   /* Copy information for the common file.
  711.      Return with a zero if any of the compares failed.  */
  712.  
  713.   for (d = 0; d < 2; d++)
  714.     for (ptr = using[d]; ptr; ptr = D_NEXT (ptr))
  715.       {
  716.     int result_offset = D_LOWLINE (ptr, FC) - lowc;
  717.  
  718.     if (!copy_stringlist (D_LINEARRAY (ptr, FC),
  719.                   D_LENARRAY (ptr, FC),
  720.                   D_LINEARRAY (result, FILEC) + result_offset,
  721.                   D_LENARRAY (result, FILEC) + result_offset,
  722.                   D_NUMLINES (ptr, FC)))
  723.       return 0;
  724.       }
  725.  
  726.   /* Copy information for file d.  First deal with anything that might be
  727.      before the first diff.  */
  728.  
  729.   for (d = 0; d < 2; d++)
  730.     {
  731.       struct diff_block *u = using[d];
  732.       int lo = low[d], hi = high[d];
  733.  
  734.       for (i = 0;
  735.        i + lo < (u ? D_LOWLINE (u, FO) : hi + 1);
  736.        i++)
  737.     {
  738.       D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, i);
  739.       D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, i);
  740.     }
  741.  
  742.       for (ptr = u; ptr; ptr = D_NEXT (ptr))
  743.     {
  744.       int result_offset = D_LOWLINE (ptr, FO) - lo;
  745.       int linec;
  746.  
  747.       if (!copy_stringlist (D_LINEARRAY (ptr, FO),
  748.                 D_LENARRAY (ptr, FO),
  749.                 D_LINEARRAY (result, FILE0 + d) + result_offset,
  750.                 D_LENARRAY (result, FILE0 + d) + result_offset,
  751.                 D_NUMLINES (ptr, FO)))
  752.         return 0;
  753.  
  754.       /* Catch the lines between here and the next diff */
  755.       linec = D_HIGHLINE (ptr, FC) + 1 - lowc;
  756.       for (i = D_HIGHLINE (ptr, FO) + 1 - lo;
  757.            i < (D_NEXT (ptr) ? D_LOWLINE (D_NEXT (ptr), FO) : hi + 1) - lo;
  758.            i++)
  759.         {
  760.           D_RELNUM (result, FILE0 + d, i) = D_RELNUM (result, FILEC, linec);
  761.           D_RELLEN (result, FILE0 + d, i) = D_RELLEN (result, FILEC, linec);
  762.           linec++;
  763.         }
  764.     }
  765.     }
  766.  
  767.   /* Set correspond */
  768.   if (!using[0])
  769.     D3_TYPE (result) = DIFF_2ND;
  770.   else if (!using[1])
  771.     D3_TYPE (result) = DIFF_1ST;
  772.   else
  773.     {
  774.       int nl0 = D_NUMLINES (result, FILE0);
  775.       int nl1 = D_NUMLINES (result, FILE1);
  776.  
  777.       if (nl0 != nl1
  778.       || !compare_line_list (D_LINEARRAY (result, FILE0),
  779.                  D_LENARRAY (result, FILE0),
  780.                  D_LINEARRAY (result, FILE1),
  781.                  D_LENARRAY (result, FILE1),
  782.                  nl0))
  783.     D3_TYPE (result) = DIFF_ALL;
  784.       else
  785.     D3_TYPE (result) = DIFF_3RD;
  786.     }
  787.  
  788.   return result;
  789. }
  790.  
  791. /*
  792.  * This routine copies pointers from a list of strings to a different list
  793.  * of strings.  If a spot in the second list is already filled, it
  794.  * makes sure that it is filled with the same string; if not it
  795.  * returns 0, the copy incomplete.
  796.  * Upon successful completion of the copy, it returns 1.
  797.  */
  798. static int
  799. copy_stringlist (fromptrs, fromlengths, toptrs, tolengths, copynum)
  800.      char *fromptrs[], *toptrs[];
  801.      int *fromlengths, *tolengths;
  802.      int copynum;
  803. {
  804.   register char
  805.     **f = fromptrs,
  806.     **t = toptrs;
  807.   register int
  808.     *fl = fromlengths,
  809.     *tl = tolengths;
  810.  
  811.   while (copynum--)
  812.     {
  813.       if (*t)
  814.     { if (*fl != *tl || bcmp (*f, *t, *fl)) return 0; }
  815.       else
  816.     { *t = *f ; *tl = *fl; }
  817.  
  818.       t++; f++; tl++; fl++;
  819.     }
  820.   return 1;
  821. }
  822.  
  823. /*
  824.  * Create a diff3_block, with ranges as specified in the arguments.
  825.  * Allocate the arrays for the various pointers (and zero them) based
  826.  * on the arguments passed.  Return the block as a result.
  827.  */
  828. static struct diff3_block *
  829. create_diff3_block (low0, high0, low1, high1, low2, high2)
  830.      register int low0, high0, low1, high1, low2, high2;
  831. {
  832.   struct diff3_block *result = ALLOCATE (1, struct diff3_block);
  833.   int numlines;
  834.  
  835.   D3_TYPE (result) = ERROR;
  836.   D_NEXT (result) = 0;
  837.  
  838.   /* Assign ranges */
  839.   D_LOWLINE (result, FILE0) = low0;
  840.   D_HIGHLINE (result, FILE0) = high0;
  841.   D_LOWLINE (result, FILE1) = low1;
  842.   D_HIGHLINE (result, FILE1) = high1;
  843.   D_LOWLINE (result, FILE2) = low2;
  844.   D_HIGHLINE (result, FILE2) = high2;
  845.  
  846.   /* Allocate and zero space */
  847.   numlines = D_NUMLINES (result, FILE0);
  848.   if (numlines)
  849.     {
  850.       D_LINEARRAY (result, FILE0) = ALLOCATE (numlines, char *);
  851.       D_LENARRAY (result, FILE0) = ALLOCATE (numlines, int);
  852.       bzero (D_LINEARRAY (result, FILE0), (numlines * sizeof (char *)));
  853.       bzero (D_LENARRAY (result, FILE0), (numlines * sizeof (int)));
  854.     }
  855.   else
  856.     {
  857.       D_LINEARRAY (result, FILE0) = (char **) 0;
  858.       D_LENARRAY (result, FILE0) = (int *) 0;
  859.     }
  860.  
  861.   numlines = D_NUMLINES (result, FILE1);
  862.   if (numlines)
  863.     {
  864.       D_LINEARRAY (result, FILE1) = ALLOCATE (numlines, char *);
  865.       D_LENARRAY (result, FILE1) = ALLOCATE (numlines, int);
  866.       bzero (D_LINEARRAY (result, FILE1), (numlines * sizeof (char *)));
  867.       bzero (D_LENARRAY (result, FILE1), (numlines * sizeof (int)));
  868.     }
  869.   else
  870.     {
  871.       D_LINEARRAY (result, FILE1) = (char **) 0;
  872.       D_LENARRAY (result, FILE1) = (int *) 0;
  873.     }
  874.  
  875.   numlines = D_NUMLINES (result, FILE2);
  876.   if (numlines)
  877.     {
  878.       D_LINEARRAY (result, FILE2) = ALLOCATE (numlines, char *);
  879.       D_LENARRAY (result, FILE2) = ALLOCATE (numlines, int);
  880.       bzero (D_LINEARRAY (result, FILE2), (numlines * sizeof (char *)));
  881.       bzero (D_LENARRAY (result, FILE2), (numlines * sizeof (int)));
  882.     }
  883.   else
  884.     {
  885.       D_LINEARRAY (result, FILE2) = (char **) 0;
  886.       D_LENARRAY (result, FILE2) = (int *) 0;
  887.     }
  888.  
  889.   /* Return */
  890.   return result;
  891. }
  892.  
  893. /*
  894.  * Compare two lists of lines of text.
  895.  * Return 1 if they are equivalent, 0 if not.
  896.  */
  897. static int
  898. compare_line_list (list1, lengths1, list2, lengths2, nl)
  899.      char *list1[], *list2[];
  900.      int *lengths1, *lengths2;
  901.      int nl;
  902. {
  903.   char
  904.     **l1 = list1,
  905.     **l2 = list2;
  906.   int
  907.     *lgths1 = lengths1,
  908.     *lgths2 = lengths2;
  909.  
  910.   while (nl--)
  911.     if (!*l1 || !*l2 || *lgths1 != *lgths2++
  912.     || bcmp (*l1++, *l2++, *lgths1++))
  913.       return 0;
  914.   return 1;
  915. }
  916.  
  917. /*
  918.  * Routines to input and parse two way diffs.
  919.  */
  920.  
  921. extern char **environ;
  922.  
  923. #define    DIFF_CHUNK_SIZE    10000
  924.  
  925. static struct diff_block *
  926. process_diff (filea, fileb, last_block)
  927.      char *filea, *fileb;
  928.      struct diff_block **last_block;
  929. {
  930.   char *diff_contents;
  931.   char *diff_limit;
  932.   char *scan_diff;
  933.   enum diff_type dt;
  934.   int i;
  935.   struct diff_block *block_list, **block_list_end, *bptr;
  936.  
  937.   diff_limit = read_diff (filea, fileb, &diff_contents);
  938.   scan_diff = diff_contents;
  939.   block_list_end = &block_list;
  940.  
  941.   while (scan_diff < diff_limit)
  942.     {
  943.       bptr = ALLOCATE (1, struct diff_block);
  944.       bptr->lines[0] = bptr->lines[1] = (char **) 0;
  945.       bptr->lengths[0] = bptr->lengths[1] = (int *) 0;
  946.  
  947.       dt = process_diff_control (&scan_diff, bptr);
  948.       if (dt == ERROR || *scan_diff != '\n')
  949.     {
  950.       fprintf (stderr, "%s: diff error: ", argv0);
  951.       do
  952.         {
  953.           putc (*scan_diff, stderr);
  954.         }
  955.       while (*scan_diff++ != '\n');
  956.       exit (2);
  957.     }
  958.       scan_diff++;
  959.  
  960.       /* Force appropriate ranges to be null, if necessary */
  961.       switch (dt)
  962.     {
  963.     case ADD:
  964.       bptr->ranges[0][0]++;
  965.       break;
  966.     case DELETE:
  967.       bptr->ranges[1][0]++;
  968.       break;
  969.     case CHANGE:
  970.       break;
  971.     default:
  972.       fatal ("internal error: invalid diff type in process_diff");
  973.       break;
  974.     }
  975.  
  976.       /* Allocate space for the pointers for the lines from filea, and
  977.      parcel them out among these pointers */
  978.       if (dt != ADD)
  979.     {
  980.       int numlines = D_NUMLINES (bptr, 0);
  981.       bptr->lines[0] = ALLOCATE (numlines, char *);
  982.       bptr->lengths[0] = ALLOCATE (numlines, int);
  983.       for (i = 0; i < numlines; i++)
  984.         scan_diff = scan_diff_line (scan_diff,
  985.                     &(bptr->lines[0][i]),
  986.                     &(bptr->lengths[0][i]),
  987.                     diff_limit,
  988.                     '<');
  989.     }
  990.  
  991.       /* Get past the separator for changes */
  992.       if (dt == CHANGE)
  993.     {
  994.       if (strncmp (scan_diff, "---\n", 4))
  995.         fatal ("invalid diff format; invalid change separator");
  996.       scan_diff += 4;
  997.     }
  998.  
  999.       /* Allocate space for the pointers for the lines from fileb, and
  1000.      parcel them out among these pointers */
  1001.       if (dt != DELETE)
  1002.     {
  1003.       int numlines = D_NUMLINES (bptr, 1);
  1004.       bptr->lines[1] = ALLOCATE (numlines, char *);
  1005.       bptr->lengths[1] = ALLOCATE (numlines, int);
  1006.       for (i = 0; i < numlines; i++)
  1007.         scan_diff = scan_diff_line (scan_diff,
  1008.                     &(bptr->lines[1][i]),
  1009.                     &(bptr->lengths[1][i]),
  1010.                     diff_limit,
  1011.                     '>');
  1012.     }
  1013.  
  1014.       /* Place this block on the blocklist.  */
  1015.       *block_list_end = bptr;
  1016.       block_list_end = &bptr->next;
  1017.     }
  1018.  
  1019.   *block_list_end = 0;
  1020.   *last_block = bptr;
  1021.   return block_list;
  1022. }
  1023.  
  1024. /*
  1025.  * This routine will parse a normal format diff control string.  It
  1026.  * returns the type of the diff (ERROR if the format is bad).  All of
  1027.  * the other important information is filled into to the structure
  1028.  * pointed to by db, and the string pointer (whose location is passed
  1029.  * to this routine) is updated to point beyond the end of the string
  1030.  * parsed.  Note that only the ranges in the diff_block will be set by
  1031.  * this routine.
  1032.  *
  1033.  * If some specific pair of numbers has been reduced to a single
  1034.  * number, then both corresponding numbers in the diff block are set
  1035.  * to that number.  In general these numbers are interpetted as ranges
  1036.  * inclusive, unless being used by the ADD or DELETE commands.  It is
  1037.  * assumed that these will be special cased in a superior routine.
  1038.  */
  1039.  
  1040. static enum diff_type
  1041. process_diff_control (string, db)
  1042.      char **string;
  1043.      struct diff_block *db;
  1044. {
  1045.   char *s = *string;
  1046.   int holdnum;
  1047.   enum diff_type type;
  1048.  
  1049. /* These macros are defined here because they can use variables
  1050.    defined in this function.  Don't try this at home kids, we're
  1051.    trained professionals!
  1052.  
  1053.    Also note that SKIPWHITE only recognizes tabs and spaces, and
  1054.    that READNUM can only read positive, integral numbers */
  1055.  
  1056. #define    SKIPWHITE(s)    { while (*s == ' ' || *s == '\t') s++; }
  1057. #define    READNUM(s, num)    \
  1058.     { if (!isdigit (*s)) return ERROR; holdnum = 0;    \
  1059.       do { holdnum = (*s++ - '0' + holdnum * 10); }    \
  1060.       while (isdigit (*s)); (num) = holdnum; }
  1061.  
  1062.   /* Read first set of digits */
  1063.   SKIPWHITE (s);
  1064.   READNUM (s, db->ranges[0][START]);
  1065.  
  1066.   /* Was that the only digit? */
  1067.   SKIPWHITE (s);
  1068.   if (*s == ',')
  1069.     {
  1070.       /* Get the next digit */
  1071.       s++;
  1072.       READNUM (s, db->ranges[0][END]);
  1073.     }
  1074.   else
  1075.     db->ranges[0][END] = db->ranges[0][START];
  1076.  
  1077.   /* Get the letter */
  1078.   SKIPWHITE (s);
  1079.   switch (*s)
  1080.     {
  1081.     case 'a':
  1082.       type = ADD;
  1083.       break;
  1084.     case 'c':
  1085.       type = CHANGE;
  1086.       break;
  1087.     case 'd':
  1088.       type = DELETE;
  1089.       break;
  1090.     default:
  1091.       return ERROR;            /* Bad format */
  1092.     }
  1093.   s++;                /* Past letter */
  1094.  
  1095.   /* Read second set of digits */
  1096.   SKIPWHITE (s);
  1097.   READNUM (s, db->ranges[1][START]);
  1098.  
  1099.   /* Was that the only digit? */
  1100.   SKIPWHITE (s);
  1101.   if (*s == ',')
  1102.     {
  1103.       /* Get the next digit */
  1104.       s++;
  1105.       READNUM (s, db->ranges[1][END]);
  1106.       SKIPWHITE (s);        /* To move to end */
  1107.     }
  1108.   else
  1109.     db->ranges[1][END] = db->ranges[1][START];
  1110.  
  1111.   *string = s;
  1112.   return type;
  1113. }
  1114.  
  1115. static char *
  1116. read_diff (filea, fileb, output_placement)
  1117.      char *filea, *fileb;
  1118.      char **output_placement;
  1119. {
  1120. #ifndef AMIGA
  1121.  
  1122.   char *argv[7];
  1123.   char horizon_arg[256];
  1124.   char **ap;
  1125.   int fds[2];
  1126.   char *diff_result;
  1127.   int current_chunk_size;
  1128.   int bytes;
  1129.   int total;
  1130.   int pid, w;
  1131.   int wstatus;
  1132.  
  1133.   ap = argv;
  1134.   *ap++ = diff_program;
  1135.   if (always_text)
  1136.     *ap++ = "-a";
  1137.   sprintf (horizon_arg, "--horizon-lines=%d", horizon_lines);
  1138.   *ap++ = horizon_arg;
  1139.   *ap++ = "--";
  1140.   *ap++ = filea;
  1141.   *ap++ = fileb;
  1142.   *ap = (char *) 0;
  1143.  
  1144.   if (pipe (fds) < 0)
  1145.     perror_with_exit ("pipe failed");
  1146.  
  1147.   pid = vfork ();
  1148.   if (pid == 0)
  1149.     {
  1150.       /* Child */
  1151.       close (fds[0]);
  1152.       if (fds[1] != fileno (stdout))
  1153.     {
  1154.       dup2 (fds[1], fileno (stdout));
  1155.       close (fds[1]);
  1156.     }
  1157.       execve (diff_program, argv, environ);
  1158.       /* Avoid stdio, because the parent process's buffers are inherited.  */
  1159.       write (fileno (stderr), diff_program, strlen (diff_program));
  1160.       write (fileno (stderr), ": not found\n", 12);
  1161.       _exit (2);
  1162.     }
  1163.  
  1164.   if (pid == -1)
  1165.     perror_with_exit ("fork failed");
  1166.  
  1167.   close (fds[1]);        /* Prevent erroneous lack of EOF */
  1168.  
  1169. #else /* AMIGA */
  1170.  
  1171.   static char diff_command_line[256];
  1172.   char horizon_arg[100];
  1173.   int fds[2];
  1174.   char *diff_result;
  1175.   int current_chunk_size;
  1176.   int bytes;
  1177.   int total;
  1178.   void (*oldsigint)();
  1179.   static long num_invocations = 0;
  1180.   char pipe_name[20];
  1181.   struct Task *Task;
  1182.   struct TagItem STags[5];
  1183.   BPTR StdOutDiff;
  1184.  
  1185.   /* The user should not be able to break the program while the child
  1186.      process is being executed, otherwise the child process will still
  1187.      be writing to the pipe-device until it deadlocks because there is
  1188.      no reader on the other side of the pipe. So prohibit breaking the
  1189.      program until the pipe is closed. */
  1190.   oldsigint = signal (SIGINT, SIG_IGN);
  1191.  
  1192.   /* Construct command line. Enclose filenames in double quotes in
  1193.      case the user specifies files with spaces in their names. */
  1194.   strcpy (diff_command_line, diff_program);
  1195.   if (always_text)
  1196.     strcat (diff_command_line, " -a");
  1197.   sprintf (horizon_arg, " --horizon-lines=%d", horizon_lines);
  1198.   strcat (diff_command_line, horizon_arg);
  1199.   strcat (diff_command_line, " --");
  1200.   strcat (diff_command_line, " \"");
  1201.   strcat (diff_command_line, filea);
  1202.   strcat (diff_command_line, "\" \"");
  1203.   strcat (diff_command_line, fileb);
  1204.   strcat (diff_command_line, "\"");
  1205.  
  1206.   /* Construct filename for the pipe to be used */
  1207.   Task = FindTask (NULL);
  1208.   num_invocations++;
  1209.   sprintf (pipe_name, "PIPE:%08lX_%ld", Task, num_invocations);
  1210.  
  1211.   /* Open pipe for child process */
  1212.   StdOutDiff = Open (pipe_name, MODE_NEWFILE);
  1213.   if (!StdOutDiff)
  1214.     perror_with_exit ("pipe failed");
  1215.  
  1216.   /* Child process runs asynchronously with pipe as stdout */
  1217.   STags[0].ti_Tag = SYS_Input;
  1218.   STags[0].ti_Data = NULL;
  1219.   STags[1].ti_Tag = SYS_Output;
  1220.   STags[1].ti_Data = StdOutDiff;
  1221.   STags[2].ti_Tag = SYS_Asynch;
  1222.   STags[2].ti_Data = TRUE;
  1223.   STags[3].ti_Tag = SYS_UserShell;
  1224.   STags[3].ti_Data = TRUE;
  1225.   STags[4].ti_Tag = TAG_DONE;
  1226.   /* Start child process */
  1227.   if ((System (diff_command_line, STags)) != 0) {
  1228.     Close (StdOutDiff);
  1229.     perror_with_exit ("diff: not found");
  1230.   }
  1231.  
  1232.   /* Open pipe for this side of the communication */
  1233.   fds[0] = open (pipe_name, O_RDONLY);
  1234.   if (fds[0] < 0) {
  1235.     Close (StdOutDiff);
  1236.     perror_with_exit ("pipe failed");
  1237.   }
  1238.  
  1239. #endif /* !AMIGA */
  1240.  
  1241.   current_chunk_size = DIFF_CHUNK_SIZE;
  1242.   diff_result = (char *) xmalloc (current_chunk_size);
  1243.   total = 0;
  1244.   do {
  1245.     bytes = myread (fds[0],
  1246.             diff_result + total,
  1247.             current_chunk_size - total);
  1248.     total += bytes;
  1249.     if (total == current_chunk_size)
  1250.       diff_result = (char *) xrealloc (diff_result, (current_chunk_size *= 2));
  1251.   } while (bytes);
  1252.  
  1253.   if (total != 0 && diff_result[total-1] != '\n')
  1254.     fatal ("invalid diff format; incomplete last line");
  1255.  
  1256.   *output_placement = diff_result;
  1257.  
  1258. #ifndef AMIGA
  1259.   do
  1260.     if ((w = wait (&wstatus)) == -1)
  1261.       perror_with_exit ("wait failed");
  1262.   while (w != pid);
  1263.  
  1264.   if (! (WIFEXITED (wstatus) && WEXITSTATUS (wstatus) < 2))
  1265.     fatal ("subsidiary diff failed");
  1266. #else /* AMIGA */
  1267.   /* Close pipe */
  1268.   close (fds[0]);
  1269.   /* Re-install break-handler */
  1270.   signal (SIGINT, oldsigint);
  1271. #endif /* !AMIGA */
  1272.  
  1273.   return diff_result + total;
  1274. }
  1275.  
  1276.  
  1277. /*
  1278.  * Scan a regular diff line (consisting of > or <, followed by a
  1279.  * space, followed by text (including nulls) up to a newline.
  1280.  *
  1281.  * This next routine began life as a macro and many parameters in it
  1282.  * are used as call-by-reference values.
  1283.  */
  1284. static char *
  1285. scan_diff_line (scan_ptr, set_start, set_length, limit, firstchar)
  1286.      char *scan_ptr, **set_start;
  1287.      int *set_length;
  1288.      char *limit;
  1289.      char firstchar;
  1290. {
  1291.   char *line_ptr;
  1292.  
  1293.   if (!(scan_ptr[0] == (firstchar)
  1294.     && scan_ptr[1] == ' '))
  1295.     fatal ("invalid diff format; incorrect leading line chars");
  1296.  
  1297.   *set_start = line_ptr = scan_ptr + 2;
  1298.   while (*line_ptr++ != '\n')
  1299.     ;
  1300.  
  1301.   /* Include newline if the original line ended in a newline,
  1302.      or if an edit script is being generated.
  1303.      Copy any missing newline message to stderr if an edit script is being
  1304.      generated, because edit scripts cannot handle missing newlines.
  1305.      Return the beginning of the next line.  */
  1306.   *set_length = line_ptr - *set_start;
  1307.   if (line_ptr < limit && *line_ptr == '\\')
  1308.     {
  1309.       if (edscript)
  1310.     fprintf (stderr, "%s:", argv0);
  1311.       else
  1312.     --*set_length;
  1313.       line_ptr++;
  1314.       do
  1315.     {
  1316.       if (edscript)
  1317.         putc (*line_ptr, stderr);
  1318.     }
  1319.       while (*line_ptr++ != '\n');
  1320.     }
  1321.  
  1322.   return line_ptr;
  1323. }
  1324.  
  1325. /*
  1326.  * This routine outputs a three way diff passed as a list of
  1327.  * diff3_block's.
  1328.  * The argument MAPPING is indexed by external file number (in the
  1329.  * argument list) and contains the internal file number (from the
  1330.  * diff passed).  This is important because the user expects his
  1331.  * outputs in terms of the argument list number, and the diff passed
  1332.  * may have been done slightly differently (if the last argument
  1333.  * was "-", for example).
  1334.  * REV_MAPPING is the inverse of MAPPING.
  1335.  */
  1336. static void
  1337. output_diff3 (outputfile, diff, mapping, rev_mapping)
  1338.      FILE *outputfile;
  1339.      struct diff3_block *diff;
  1340.      int mapping[3], rev_mapping[3];
  1341. {
  1342.   int i;
  1343.   int oddoneout;
  1344.   char *cp;
  1345.   struct diff3_block *ptr;
  1346.   int line;
  1347.   int length;
  1348.   int dontprint;
  1349.   static int skew_increment[3] = { 2, 3, 1 }; /* 0==>2==>1==>3 */
  1350.  
  1351.   for (ptr = diff; ptr; ptr = D_NEXT (ptr))
  1352.     {
  1353.       char x[2];
  1354.  
  1355.       switch (ptr->correspond)
  1356.     {
  1357.     case DIFF_ALL:
  1358.       x[0] = '\0';
  1359.       dontprint = 3;    /* Print them all */
  1360.       oddoneout = 3;    /* Nobody's odder than anyone else */
  1361.       break;
  1362.     case DIFF_1ST:
  1363.     case DIFF_2ND:
  1364.     case DIFF_3RD:
  1365.       oddoneout = rev_mapping[(int) ptr->correspond - (int) DIFF_1ST];
  1366.  
  1367.       x[0] = oddoneout + '1';
  1368.       x[1] = '\0';
  1369.       dontprint = oddoneout==0;
  1370.       break;
  1371.     default:
  1372.       fatal ("internal error: invalid diff type passed to output");
  1373.     }
  1374.       fprintf (outputfile, "====%s\n", x);
  1375.  
  1376.       /* Go 0, 2, 1 if the first and third outputs are equivalent.  */
  1377.       for (i = 0; i < 3;
  1378.        i = (oddoneout == 1 ? skew_increment[i] : i + 1))
  1379.     {
  1380.       int realfile = mapping[i];
  1381.       int
  1382.         lowt = D_LOWLINE (ptr, realfile),
  1383.         hight = D_HIGHLINE (ptr, realfile);
  1384.  
  1385.       fprintf (outputfile, "%d:", i + 1);
  1386.       switch (lowt - hight)
  1387.         {
  1388.         case 1:
  1389.           fprintf (outputfile, "%da\n", lowt - 1);
  1390.           break;
  1391.         case 0:
  1392.           fprintf (outputfile, "%dc\n", lowt);
  1393.           break;
  1394.         default:
  1395.           fprintf (outputfile, "%d,%dc\n", lowt, hight);
  1396.           break;
  1397.         }
  1398.  
  1399.       if (i == dontprint) continue;
  1400.  
  1401.       for (line = 0; line < hight - lowt + 1; line++)
  1402.         {
  1403.           fprintf (outputfile, "  ");
  1404.           cp = D_RELNUM (ptr, realfile, line);
  1405.           length = D_RELLEN (ptr, realfile, line);
  1406.           fwrite (cp, sizeof (char), length, outputfile);
  1407.         }
  1408.       if (line != 0 && cp[length - 1] != '\n')
  1409.         fprintf (outputfile, "\n\\ No newline at end of file\n");
  1410.     }
  1411.     }
  1412. }
  1413.  
  1414.  
  1415. /*
  1416.  * Output to OUTPUTFILE the lines of B taken from FILENUM.
  1417.  * Double any initial '.'s; yield nonzero if any initial '.'s were doubled.
  1418.  */
  1419. static int
  1420. dotlines (outputfile, b, filenum)
  1421.      FILE *outputfile;
  1422.      struct diff3_block *b;
  1423.      int filenum;
  1424. {
  1425.   int i;
  1426.   int leading_dot = 0;
  1427.  
  1428.   for (i = 0;
  1429.        i < D_NUMLINES (b, filenum);
  1430.        i++)
  1431.     {
  1432.       char *line = D_RELNUM (b, filenum, i);
  1433.       if (line[0] == '.')
  1434.     {
  1435.       leading_dot = 1;
  1436.       fprintf (outputfile, ".");
  1437.     }
  1438.       fwrite (line, sizeof (char),
  1439.           D_RELLEN (b, filenum, i), outputfile);
  1440.     }
  1441.  
  1442.   return leading_dot;
  1443. }
  1444.  
  1445. /*
  1446.  * Output to OUTPUTFILE a '.' line.  If LEADING_DOT is nonzero,
  1447.  * also output a command that removes initial '.'s
  1448.  * starting with line START and continuing for NUM lines.
  1449.  */
  1450. static void
  1451. undotlines (outputfile, leading_dot, start, num)
  1452.      FILE *outputfile;
  1453.      int leading_dot, start, num;
  1454. {
  1455.   fprintf (outputfile, ".\n");
  1456.   if (leading_dot)
  1457.     if (num == 1)
  1458.       fprintf (outputfile, "%ds/^\\.//\n", start);
  1459.     else
  1460.       fprintf (outputfile, "%d,%ds/^\\.//\n", start, start + num - 1);
  1461. }
  1462.  
  1463. /*
  1464.  * This routine outputs a diff3 set of blocks as an ed script.  This
  1465.  * script applies the changes between file's 2 & 3 to file 1.  It
  1466.  * takes the precise format of the ed script to be output from global
  1467.  * variables set during options processing.  Note that it does
  1468.  * destructive things to the set of diff3 blocks it is passed; it
  1469.  * reverses their order (this gets around the problems involved with
  1470.  * changing line numbers in an ed script).
  1471.  *
  1472.  * Note that this routine has the same problem of mapping as the last
  1473.  * one did; the variable MAPPING maps from file number according to
  1474.  * the argument list to file number according to the diff passed.  All
  1475.  * files listed below are in terms of the argument list.
  1476.  * REV_MAPPING is the inverse of MAPPING.
  1477.  *
  1478.  * The arguments FILE0, FILE1 and FILE2 are the strings to print
  1479.  * as the names of the three files.  These may be the actual names,
  1480.  * or may be the arguments specified with -L.
  1481.  *
  1482.  * Returns 1 if conflicts were found.
  1483.  */
  1484.  
  1485. static int
  1486. output_diff3_edscript (outputfile, diff, mapping, rev_mapping,
  1487.                file0, file1, file2)
  1488.      FILE *outputfile;
  1489.      struct diff3_block *diff;
  1490.      int mapping[3], rev_mapping[3];
  1491.      char *file0, *file1, *file2;
  1492. {
  1493.   int leading_dot;
  1494.   int conflicts_found = 0, conflict;
  1495.   struct diff3_block *b;
  1496.  
  1497.   for (b = reverse_diff3_blocklist (diff); b; b = b->next)
  1498.     {
  1499.       /* Must do mapping correctly.  */
  1500.       enum diff_type type
  1501.     = ((b->correspond == DIFF_ALL) ?
  1502.        DIFF_ALL :
  1503.        ((enum diff_type)
  1504.         (((int) DIFF_1ST)
  1505.          + rev_mapping[(int) b->correspond - (int) DIFF_1ST])));
  1506.  
  1507.       /* If we aren't supposed to do this output block, skip it.  */
  1508.       switch (type)
  1509.     {
  1510.     default: continue;
  1511.     case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break;
  1512.     case DIFF_3RD: if (overlap_only) continue; conflict = 0; break;
  1513.     case DIFF_ALL: if (simple_only) continue; conflict = flagging; break;
  1514.     }
  1515.  
  1516.       if (conflict)
  1517.     {
  1518.       conflicts_found = 1;
  1519.  
  1520.  
  1521.       /* Mark end of conflict.  */
  1522.  
  1523.       fprintf (outputfile, "%da\n", D_HIGHLINE (b, mapping[FILE0]));
  1524.       leading_dot = 0;
  1525.       if (type == DIFF_ALL)
  1526.         {
  1527.           if (show_2nd)
  1528.         {
  1529.           /* Append lines from FILE1.  */
  1530.           fprintf (outputfile, "||||||| %s\n", file1);
  1531.           leading_dot = dotlines (outputfile, b, mapping[FILE1]);
  1532.         }
  1533.           /* Append lines from FILE2.  */
  1534.           fprintf (outputfile, "=======\n");
  1535.           leading_dot |= dotlines (outputfile, b, mapping[FILE2]);
  1536.         }
  1537.       fprintf (outputfile, ">>>>>>> %s\n", file2);
  1538.       undotlines (outputfile, leading_dot,
  1539.               D_HIGHLINE (b, mapping[FILE0]) + 2,
  1540.               (D_NUMLINES (b, mapping[FILE1])
  1541.                + D_NUMLINES (b, mapping[FILE2]) + 1));
  1542.  
  1543.  
  1544.       /* Mark start of conflict.  */
  1545.  
  1546.       fprintf (outputfile, "%da\n<<<<<<< %s\n",
  1547.            D_LOWLINE (b, mapping[FILE0]) - 1,
  1548.            type == DIFF_ALL ? file0 : file1);
  1549.       leading_dot = 0;
  1550.       if (type == DIFF_2ND)
  1551.         {
  1552.           /* Prepend lines from FILE1.  */
  1553.           leading_dot = dotlines (outputfile, b, mapping[FILE1]);
  1554.           fprintf (outputfile, "=======\n");
  1555.         }
  1556.       undotlines (outputfile, leading_dot,
  1557.               D_LOWLINE (b, mapping[FILE0]) + 1,
  1558.               D_NUMLINES (b, mapping[FILE1]));
  1559.     }
  1560.       else if (D_NUMLINES (b, mapping[FILE2]) == 0)
  1561.     /* Write out a delete */
  1562.     {
  1563.       if (D_NUMLINES (b, mapping[FILE0]) == 1)
  1564.         fprintf (outputfile, "%dd\n",
  1565.              D_LOWLINE (b, mapping[FILE0]));
  1566.       else
  1567.         fprintf (outputfile, "%d,%dd\n",
  1568.              D_LOWLINE (b, mapping[FILE0]),
  1569.              D_HIGHLINE (b, mapping[FILE0]));
  1570.     }
  1571.       else
  1572.     /* Write out an add or change */
  1573.     {
  1574.       switch (D_NUMLINES (b, mapping[FILE0]))
  1575.         {
  1576.         case 0:
  1577.           fprintf (outputfile, "%da\n",
  1578.                D_HIGHLINE (b, mapping[FILE0]));
  1579.           break;
  1580.         case 1:
  1581.           fprintf (outputfile, "%dc\n",
  1582.                D_HIGHLINE (b, mapping[FILE0]));
  1583.           break;
  1584.         default:
  1585.           fprintf (outputfile, "%d,%dc\n",
  1586.                D_LOWLINE (b, mapping[FILE0]),
  1587.                D_HIGHLINE (b, mapping[FILE0]));
  1588.           break;
  1589.         }
  1590.  
  1591.       undotlines (outputfile, dotlines (outputfile, b, mapping[FILE2]),
  1592.               D_LOWLINE (b, mapping[FILE0]),
  1593.               D_NUMLINES (b, mapping[FILE2]));
  1594.     }
  1595.     }
  1596.   if (finalwrite) fprintf (outputfile, "w\nq\n");
  1597.   return conflicts_found;
  1598. }
  1599.  
  1600. /*
  1601.  * Read from INFILE and output to OUTPUTFILE a set of diff3_ blocks DIFF
  1602.  * as a merged file.  This acts like 'ed file0 <[output_diff3_edscript]',
  1603.  * except that it works even for binary data or incomplete lines.
  1604.  *
  1605.  * As before, MAPPING maps from arg list file number to diff file number,
  1606.  * REV_MAPPING is its inverse,
  1607.  * and FILE0, FILE1, and FILE2 are the names of the files.
  1608.  *
  1609.  * Returns 1 if conflicts were found.
  1610.  */
  1611.  
  1612. static int
  1613. output_diff3_merge (infile, outputfile, diff, mapping, rev_mapping,
  1614.             file0, file1, file2)
  1615.      FILE *infile, *outputfile;
  1616.      struct diff3_block *diff;
  1617.      int mapping[3], rev_mapping[3];
  1618.      char *file0, *file1, *file2;
  1619. {
  1620.   int c, i;
  1621.   int conflicts_found = 0, conflict;
  1622.   struct diff3_block *b;
  1623.   int linesread = 0;
  1624.  
  1625.   for (b = diff; b; b = b->next)
  1626.     {
  1627.       /* Must do mapping correctly.  */
  1628.       enum diff_type type
  1629.     = ((b->correspond == DIFF_ALL) ?
  1630.        DIFF_ALL :
  1631.        ((enum diff_type)
  1632.         (((int) DIFF_1ST)
  1633.          + rev_mapping[(int) b->correspond - (int) DIFF_1ST])));
  1634.       char *format_2nd = "<<<<<<< %s\n";
  1635.  
  1636.       /* If we aren't supposed to do this output block, skip it.  */
  1637.       switch (type)
  1638.     {
  1639.     default: continue;
  1640.     case DIFF_2ND: if (!show_2nd) continue; conflict = 1; break;
  1641.     case DIFF_3RD: if (overlap_only) continue; conflict = 0; break;
  1642.     case DIFF_ALL: if (simple_only) continue; conflict = flagging;
  1643.       format_2nd = "||||||| %s\n";
  1644.       break;
  1645.     }
  1646.  
  1647.       /* Copy I lines from file 0.  */
  1648.       i = D_LOWLINE (b, FILE0) - linesread - 1;
  1649.       linesread += i;
  1650.       while (0 <= --i)
  1651.     do
  1652.       {
  1653.         c = getc (infile);
  1654.         if (c == EOF)
  1655.           if (ferror (infile))
  1656.         perror_with_exit ("input file");
  1657.           else if (feof (infile))
  1658.         fatal ("input file shrank");
  1659.         putc (c, outputfile);
  1660.       }
  1661.     while (c != '\n');
  1662.  
  1663.       if (conflict)
  1664.     {
  1665.       conflicts_found = 1;
  1666.  
  1667.       if (type == DIFF_ALL)
  1668.         {
  1669.           /* Put in lines from FILE0 with bracket.  */
  1670.           fprintf (outputfile, "<<<<<<< %s\n", file0);
  1671.           for (i = 0;
  1672.            i < D_NUMLINES (b, mapping[FILE0]);
  1673.            i++)
  1674.         fwrite (D_RELNUM (b, mapping[FILE0], i), sizeof (char),
  1675.             D_RELLEN (b, mapping[FILE0], i), outputfile);
  1676.         }
  1677.  
  1678.       if (show_2nd)
  1679.         {
  1680.           /* Put in lines from FILE1 with bracket.  */
  1681.           fprintf (outputfile, format_2nd, file1);
  1682.           for (i = 0;
  1683.            i < D_NUMLINES (b, mapping[FILE1]);
  1684.            i++)
  1685.         fwrite (D_RELNUM (b, mapping[FILE1], i), sizeof (char),
  1686.             D_RELLEN (b, mapping[FILE1], i), outputfile);
  1687.         }
  1688.  
  1689.       fprintf (outputfile, "=======\n");
  1690.     }
  1691.  
  1692.       /* Put in lines from FILE2.  */
  1693.       for (i = 0;
  1694.        i < D_NUMLINES (b, mapping[FILE2]);
  1695.        i++)
  1696.     fwrite (D_RELNUM (b, mapping[FILE2], i), sizeof (char),
  1697.         D_RELLEN (b, mapping[FILE2], i), outputfile);
  1698.  
  1699.       if (conflict)
  1700.     fprintf (outputfile, ">>>>>>> %s\n", file2);
  1701.  
  1702.       /* Skip I lines in file 0.  */
  1703.       i = D_NUMLINES (b, FILE0);
  1704.       linesread += i;
  1705.       while (0 <= --i)
  1706.     while ((c = getc (infile)) != '\n')
  1707.       if (c == EOF)
  1708.         if (ferror (infile))
  1709.           perror_with_exit ("input file");
  1710.         else if (feof (infile))
  1711.           {
  1712.         if (i || b->next)
  1713.           fatal ("input file shrank");
  1714.         return conflicts_found;
  1715.           }
  1716.     }
  1717.   /* Copy rest of common file.  */
  1718.   while ((c = getc (infile)) != EOF || !(ferror (infile) | feof (infile)))
  1719.     putc (c, outputfile);
  1720.   return conflicts_found;
  1721. }
  1722.  
  1723. /*
  1724.  * Reverse the order of the list of diff3 blocks.
  1725.  */
  1726. static struct diff3_block *
  1727. reverse_diff3_blocklist (diff)
  1728.      struct diff3_block *diff;
  1729. {
  1730.   register struct diff3_block *tmp, *next, *prev;
  1731.  
  1732.   for (tmp = diff, prev = (struct diff3_block *) 0;
  1733.        tmp; tmp = next)
  1734.     {
  1735.       next = tmp->next;
  1736.       tmp->next = prev;
  1737.       prev = tmp;
  1738.     }
  1739.  
  1740.   return prev;
  1741. }
  1742.  
  1743. static int
  1744. myread (fd, ptr, size)
  1745.      int fd, size;
  1746.      char *ptr;
  1747. {
  1748.   int result = read (fd, ptr, size);
  1749.   if (result < 0)
  1750.     perror_with_exit ("read failed");
  1751.   return result;
  1752. }
  1753.  
  1754. VOID *
  1755. xmalloc (size)
  1756.      unsigned size;
  1757. {
  1758.   VOID *result = (VOID *) malloc (size ? size : 1);
  1759.   if (!result)
  1760.     fatal ("virtual memory exhausted");
  1761.   return result;
  1762. }
  1763.  
  1764. static VOID *
  1765. xrealloc (ptr, size)
  1766.      VOID *ptr;
  1767.      unsigned size;
  1768. {
  1769.   VOID *result = (VOID *) realloc (ptr, size ? size : 1);
  1770.   if (!result)
  1771.     fatal ("virtual memory exhausted");
  1772.   return result;
  1773. }
  1774.  
  1775. static void
  1776. fatal (string)
  1777.      char *string;
  1778. {
  1779.   fprintf (stderr, "%s: %s\n", argv0, string);
  1780.   exit (2);
  1781. }
  1782.  
  1783. static void
  1784. perror_with_exit (string)
  1785.      char *string;
  1786. {
  1787.   int e = errno;
  1788.   fprintf (stderr, "%s: ", argv0);
  1789.   errno = e;
  1790.   perror (string);
  1791.   exit (2);
  1792. }
  1793.